package nu.aing.algo;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedHashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Set;
import java.util.concurrent.atomic.AtomicReference;
import java.util.concurrent.atomic.AtomicReferenceArray;


public class GraphMain {

    public static void main(String[] args) {
        GraphMain main = new GraphMain();
        System.out.println(main.isComposite(2) );
        System.out.println(main.isComposite(3) );
        System.out.println(main.isComposite(5) );
        System.out.println(main.isComposite(7) );
        System.out.println(main.isComposite(4) );
        System.out.println(main.isComposite(41) );
        
        Graph graph = new Graph(1,2,3,4,5,6,7,8,9);
        graph.addEdge(1, 2);
        graph.addEdge(1, 4);
        graph.addEdge(1, 8);
        graph.addEdge(1, 5);
        
        graph.addEdge(2, 3);
        graph.addEdge(2, 7);
        graph.addEdge(2, 1);
        
        graph.addEdge(3, 2);
        graph.addEdge(3, 7);
        
        graph.addEdge(4, 1);
        graph.addEdge(4, 8);
        graph.addEdge(4, 6);
        
        graph.addEdge(5, 1);
        graph.addEdge(5, 8);
        
        graph.addEdge(6, 4);
        graph.addEdge(6, 7);
        
        graph.addEdge(7, 2);
        graph.addEdge(7, 3);
        graph.addEdge(7, 6);
        
        graph.addEdge(8, 1);
        graph.addEdge(8, 4);
        graph.addEdge(8, 5);
        graph.addEdge(8, 9);
        
        graph.addEdge(9, 8);
        
        graph.hasPath(1, 9);
        
    }
    
    private boolean isComposite(int n) {
        for (int i = 2; i <= n / 2; i++) {
            if (n % i == 0) {
                return true;
            }
        }
        return false;
    }
    
}

class Graph {
    
    List<Node> nodes;
    
    public Graph(int... coords) {
        nodes = new ArrayList<Node>();
        nodes.add(new Node(0));
        Arrays.sort(coords);
        for(int coord : coords) {
            nodes.add(new Node(coord));
        }
    }
    
    void addEdge(int a, int b) {
        nodes.get(a).addNeighbours(nodes.get(b));
    }
    
    void walk(Node origin, Set<Node> visited) {
        for(Node node : origin.getNeighbours() ) {
            if(!visited.contains(node) ) {
                visited.add(node);
                walk(node, visited);
            }
        }
    }
    
    boolean hasPath(int a, int b) {
        return hasPath(getNode(a), getNode(b));
    }
    
    boolean hasPath(Node origin, Node target) {
        Set<Node> visited = new LinkedHashSet<Node>();
        walk(origin, visited);
        return visited.contains(target);
    }
    
    Node getNode(int a) {
        return nodes.get(a);
    }
}

class Node {
    
    int coord;
    Set<Node> neighbours;
    
    public Node(int coord) {
        this.coord = coord;
        neighbours = new LinkedHashSet<Node>();
    }
    
    Set<Node> getNeighbours() {
        return neighbours;
    }
    
    void addNeighbours(Node neighbour) {
        neighbours.add(neighbour);
    }
    
    @Override
    public String toString() {
        return String.valueOf(coord);
    }
}